package com.zm.demo.core.sort;

import java.util.Arrays;
import java.util.Random;

import static java.lang.System.out;

/**
 * 归并排序
 * @author zoum
 * @create 2020/3/10 12:45
 */
public class MergeSort {



    public static void main(String[] args){
        Integer[] s = new Integer[new Random().nextInt(500)];
        for (int i = 0; i < s.length; i++) {
            s[i] = new Random().nextInt(1000);
        }
        out.println(Arrays.toString(s));
        out.println(Arrays.toString(mergeSort(s)));

    }


    public static Integer[] mergeSort(Integer[] ary){
        if (ary == null || ary.length <= 1){
            return ary;
        }else {
            int length = ary.length;
            int mid = length/2;
            Integer[]left = Arrays.copyOfRange(ary, 0, mid);
            Integer[]right = Arrays.copyOfRange(ary, mid, length);
            return merge(mergeSort(left), mergeSort(right));
        }
    }

    public static Integer[] merge(Integer[] left, Integer[] right){
        Integer[] result = new Integer[left.length + right.length];
        //遍历left,right，按顺序放入result
        for (int leftIndex = 0, rightIndex=0, resultIndex=0 ; resultIndex < result.length ; resultIndex++) {
            if (leftIndex >= left.length){
                result[resultIndex] = right[rightIndex++];
            }else if (rightIndex >= right.length){
                result[resultIndex] = left[leftIndex++];
            }else if (left[leftIndex] > right[rightIndex]){
                result[resultIndex] = left[leftIndex++];
            }else {
                result[resultIndex] = right[rightIndex++];
            }
        }
        return result;
    }
}
